package com.gaogzhen.algorithms4.foundation;

/**
 * union-find 默认实现
 */
public abstract class AbstractUnionFind implements UnionFind{

    /**
     * 触点所在分量标志
     */
    private int[] id;

    /**
     * 连通分量数量
     */
    private int count;


    /**
     * 初始化数组id
     * @param n 数组长度
     */
    public AbstractUnionFind(int n) {
        if (n < 0) throw new IllegalArgumentException();
        count = n;
        id = new int[n];
        for (int i = 0; i < n; i++)
            id[i] = i;
    }


    /**
     * 获取触点i对应的分量值
     * @param index 触点i
     * @return  触点对应的分量标志
     */
    protected int getId(int index) {
        return id[index];
    }

    /**
     * 设置触点i对应的分量值
     * @param index 触点index
     * @param val 分量值
     */
    protected void setId(int index, int val) {
        this.id[index] = val;
    }

    /**
     * 数组id长度
     * @return 数组id长度
     */
    protected int capacity() {
        return id.length;
    }


    /**
     * 分量数量减1
     */
    protected void decreaseCount() {
        count--;
    }

    /**
     * 连通分量的数量
     *
     * @return 数量 (between {@code 1} and {@code n})
     */
    @Override
    public int count() {
        return count;
    }

    /**
     * 校验触点p是否合法
     * @param  p 触点p
     */

    protected void validate(int p) {
        int n = id.length;
        if (p < 0 || p >= n) {
            throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n-1));
        }
    }

    /**
     * 判断触点p和触点q是否相连
     *
     * @param  p 触点p
     * @param  q 触点q
     * @return {@code true} 如果 {@code p} 和 {@code q} 相连;
     *         {@code false} 否则
     */
    @Deprecated
    @Override
    public boolean connected(int p, int q) {
        validate(p);
        validate(q);
        return find(p) == find(q);
    }
}
